package adt.subset;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import adt.queue.*;
import adt.stack.*;
/**
 * The GenerateSubsSets class can be used to generate a power set of one given set. The power set consists in all
 * sets that can be generate from the initial set.
 * Consider the example below:
 * From a initial SET {1,2,3,4}, the power set that will be generate is:
 * {{},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}
 * 
 * @author Carla Sukeyosi, Jessika Renally, Lais Camilo, Tiaraju Smaneoto
 *
 * @version 1.0
 */

public class GenerateSubSets<T> {

	private Set<Set<T>> resultSet = new HashSet<Set<T>>();
	private StackImpl<T> stack;
	private Set<T> auxSet;
	private QueueImpl<T> queue;
	private QueueImpl<T> auxQueue;
	
	/**
	 * Generates the power set of one set. This power set consists in all possible subsets which could be
	 * generated from the set.  
	 * @param set the set that will be consider to generate the power set.
	 * @return An set of sets, with size 2^n( n = set's size ), that contains all the possible subsets from the initial set. The power set it is not necessary in order.
	 */
	public Set<Set<T>> subSets(Set<T> set){
		generateSubSets(set);
		
		return resultSet;
	}
	
	private Queue<T> cloneQueue(Queue<T> Q){
		List<T> arrayTemp = new ArrayList<T>();
		while(!Q.isEmpty()){
			try {
				arrayTemp.add(Q.dequeue());
			} catch (QueueUnderflowException e) {				
				e.printStackTrace();
			}
		}
		
		Queue<T> auxQueue = new QueueImpl<T>(arrayTemp.size());
		for(int i = 0;i <arrayTemp.size(); i++){
			try {
				auxQueue.enqueue(arrayTemp.get(i));
				Q.enqueue(arrayTemp.get(i));
			} catch (QueueOverflowException e) {
				e.printStackTrace();
			}
			
		}
		return auxQueue;
	}
	//this part of the algorithm generate the basic case, all  subsets with 2 elements, if it is possible.
	private void generateBasicSubSet(Set<T> set){
		resultSet.add(new HashSet<T>());
		T[] array=  ((T[]) set.toArray());
		stack = new StackImpl<T>(array.length);
		queue = (QueueImpl<T>) new QueueImpl<T>(array.length);
		
		for(int i = 0; i < array.length; i++){
			try {
				queue.enqueue(array[i]);
			} catch (QueueOverflowException e) {
				e.printStackTrace();
			}
		}
		
		auxQueue = (QueueImpl<T>) cloneQueue(queue);
		for(int i = 0; i <array.length;i++){
			try {
				stack.push(auxQueue.dequeue());
			} catch (StackOverflowException e) {
				e.printStackTrace();
			} catch (QueueUnderflowException e) {
				e.printStackTrace();
			}
			
			try {
				queue.dequeue();
			} catch (QueueUnderflowException e) {
				e.printStackTrace();
			}
			
			while(!auxQueue.isEmpty()){
				
				try {
					stack.push(auxQueue.dequeue());
				} catch (StackOverflowException e) {
					e.printStackTrace();
				} catch (QueueUnderflowException e) {
					e.printStackTrace();
				}
				
				auxSet = new HashSet<T>();
				T e1 = null;
				try {
					e1 = stack.pop();
				} catch (StackUnderflowException e) {
					e.printStackTrace();
				}
				
				if(!e1.equals(stack.top())){
					auxSet.add(stack.top());
					auxSet.add(e1);
					if(!(resultSet.contains(auxSet))){
						resultSet.add(auxSet);
					}
				}
			}
			try {
				stack.pop();
			} catch (StackUnderflowException e) {
				e.printStackTrace();
			}
			auxQueue = (QueueImpl<T>) cloneQueue(queue);
		}
		
		 
	}
	//using the basic subsets formed, this part generates all the possible subsets to complete the power set.
	@SuppressWarnings("unchecked")
	private void generateSubSets(Set<T> set){
		generateBasicSubSet(set);	
		T[] array = ((T[]) set.toArray());
		QueueImpl<Set<T>> auxfila = new QueueImpl<Set<T>>((int) Math.pow(2, array.length));
		stack = new StackImpl<T>(array.length);
		queue = (QueueImpl<T>) new QueueImpl<T>(array.length);
		
		for(int i = 0; i < resultSet.size(); i++){
			try {
				auxfila.enqueue(((Set<T>) resultSet.toArray()[i]));
			} catch (QueueOverflowException e) {
				e.printStackTrace();
			}
		}	
		while(resultSet.size()<(Math.pow(2, set.size()))){
			for(int i = 0; i < array.length; i++){
				try {
					queue.enqueue(array[i]);
				} catch (QueueOverflowException e) {
					e.printStackTrace();
				} 
			}
			Set<T> t = null;
			try {
				t = auxfila.dequeue();
			} catch (QueueUnderflowException e) {
				e.printStackTrace();
			}
			while(!queue.isEmpty()){
				Set<T> t2 = new HashSet<T>();
				for(int i = 0; i < t.size(); i++){
					t2.add((T) t.toArray()[i]);
				}
				T element = null;
				try {
					element = queue.dequeue();
				} catch (QueueUnderflowException e) {
					e.printStackTrace();
				}
				t2.add(element);
				if(!resultSet.contains(t2)){
					resultSet.add(t2);
					try {
						auxfila.enqueue(t2);
					} catch (QueueOverflowException e) {
						e.printStackTrace();
					}
				}
			}		
		}
	}
}
